package leetcode.editor.cn;

/**
 * @id: 5
 * @title: 最长回文子串
 */
 
//给你一个字符串 s，找到 s 中最长的回文子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 示例 3： 
//
// 
//输入：s = "a"
//输出："a"
// 
//
// 示例 4： 
//
// 
//输入：s = "ac"
//输出："a"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母（大写和/或小写）组成 
// 
// Related Topics 字符串 动态规划 
// 👍 3969 👎 0

public class P5LongestPalindromicSubstring {
    public static void main(String[] args) {
        Solution solution = new P5LongestPalindromicSubstring().new Solution();
        // todo
        String result = solution.longestPalindrome("ccc");
        System.out.println(result);
    }
    
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String longestPalindrome(String s) {
        if (s.length() <= 1) {
            return s;
        }
        int[][] dp = new int[s.length()][s.length()];
        int max = 1; // 最起码单个字符是回文
        int start = 0;
        // 初始化单个字符肯定是回文
        for (int i = 0 ; i < s.length() ; i++)
            dp[i][i] = 1;
        // 行
        for (int i = 1 ; i < s.length() ; i++) {
            // 列
            for (int j = 0 ; j < i ; j++) {
                // 如果子串长度为2，两个相等就是回文
                final int len = Math.abs(i-j+1);
                final boolean eq = s.charAt(i) == s.charAt(j);
                if (len <= 2 && eq) {
                    dp[i][j] = 1;
                }
                // 如果dp[i-1][j+1]是回文，头尾相等就是回文
                if (dp[i-1][j+1] == 1 && eq) {
                    dp[i][j] = 1;
                }
                // 比之前匹配的子串要长，而且为回文
                if (dp[i][j] == 1 && len > max) {
                    start = j;
                    max = len;
                }
            }
        }
        return s.substring(start, start+max);
    }
}
//leetcode submit region end(Prohibit modification and deletion)


}